package 复习.面试TOP101.二叉树;

public class 二叉搜索树与双向链表 {
    TreeNode pre = null;
    TreeNode root = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        solve(pRootOfTree);
        return root;
    }

    public void solve(TreeNode pRoot){
        if(pRoot == null) return;

        solve(pRoot.left);

        pRoot.left = pre;
        if(pre == null){
            root = pRoot;
        }else{
            pre.right = pRoot;
        }
        pre = pRoot;

        solve(pRoot.right);
    }
}
/*
public class Solution {
    TreeNode head = null;//标记头节点
    TreeNode pre = null;//标记当前节点的前一个节点
    public TreeNode Convert(TreeNode pRootOfTree) {
        solve(pRootOfTree);
        return head;
    }

    public void solve(TreeNode root){
        if(root == null) return;
        //开始前序遍历
        solve(root.left);
        //首先把当前节点的左子针指向前序遍历的前一个节点
        root.left = pre;
        //如果说前一个节点为null，那么当前节点就是头结点，也就是最最左边的节点
        if(pre == null){
            head = root;
        }else{//如果不为空前节点的右子树指向当前节点
            pre.right = root;
        }
        //然后更新前节点的值
        pre = root;
        solve(root.right);
    }
}
 */